package com.neuedu.linkedlist;

import java.util.Iterator;

public class DoubleLinkedListSentinel implements Iterable<Integer>{//双向链表
    private final Node head;
    private final Node tail;

    public DoubleLinkedListSentinel() {
        head = new Node(null,null,666);
        tail = new Node(null,null,999);
        head.next = tail;
        tail.prev = head;
    }
    //findNode addFirst removeFirst addLast removeLast insert remove illegalIndex iterator
    public Node findNode(int index){
        int i = -1;
        for (Node cur = head ; cur != tail ; cur = cur.next , i++ ){//cur当前指针
            if (index == i){
                return cur;
            }
        }
        return null;
    }

    public void addFirst(int value){//调用insert
        insert(0,value);
//        Node cur = head;
//        Node next = head.next;
//        new Node(head,next,value);
    }
    private void insert(int index , int value){
        Node prev = findNode(index - 1);
        if (prev == null){
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node cur = new Node(prev, next, value);
        prev.next = cur;
        next.prev = cur;
    }
    public void remove(int index){
        Node remove = findNode(index);
        if (remove==head||remove==tail){
            throw illegalIndex(index);
        }

        Node prev = remove.prev;
        Node next = remove.next;
        prev.next = next;
        next.prev = prev;
    }

    public void removeFirst(){
//        Node cur = head;
//        if (cur.next == tail){
//            throw illegalIndex(0);
//        }
//        Node first = findNode(0);
//        Node next = first.next;
//        cur.next = next;
//        next.prev = cur;
        remove(0);
    }

    public void addLast(int value){//因为是链表，直接prev，就可以找到tail节点的上一个元素
        Node prev = tail.prev;
        Node added = new Node(prev, tail, value);
        prev.next = added;
        tail.prev = added;

    }

    public void removeLast(){
        if (tail.prev==head){
            throw illegalIndex(0);
        }
        if (tail.prev != head){
            Node delete = tail.prev;//要删除的节点
            Node prev = delete.prev;
            prev.next = tail;
            tail.prev = prev;
        }
    }


    private IllegalArgumentException illegalIndex(int index){
        return new IllegalArgumentException(String.format("索引[%d]不合法%n",index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node cur = head.next;//从第一个元素开始
            @Override
            public boolean hasNext() {
                return cur != tail;
            }

            @Override
            public Integer next() {
                Integer value = cur.value;
                cur = cur.next;
                return value;
            }
        };
    }


    static class Node{
        Node prev;
        Node next;
        Integer value;

        public Node(Node prev, Node next, Integer value) {
            this.prev = prev;
            this.next = next;
            this.value = value;
        }
    }
}
